package com.xiaojianhx.demo.algorithm.search;

import java.util.Arrays;

/**
 * 04 斐波那契
 * 
 * @author xiaojianhx
 * @version V1.0.0 $ 2021-08-30 23:31:02 init ---- xiaojianhx
 */
public class Algorithm_Search_04_FibonacciSearch {

    public static int search(int[] arr, int num) {

        var length = arr.length;

        var fibIdx = 0;
        var fib = fibonacciArr(length);

        // 找到大于等于数组长度的最小斐波那契数列元素
        while (length > fib[fibIdx] - 1) {
            fibIdx++;
        }

        // 将数组扩展到斐波那契数列元素的长度
        var temp = Arrays.copyOf(arr, fib[fibIdx] - 1);

        // 将扩展部分用数组最后一个元素填充
        for (var i = length; i < temp.length; i++) {
            temp[i] = arr[length - 1];
        }

        var low = 0;
        var high = length - 1;

        while (low <= high) {

            var mid = low + fib[fibIdx - 1] - 1;

            if (num < temp[mid]) {

                high = mid - 1;
                fibIdx -= 1;
            } else if (num > temp[mid]) {

                low = mid + 1;
                fibIdx -= 2;
            } else {
                return Math.min(mid, length - 1);
            }
        }

        return -1;
    }

    private static int[] fibonacciArr(int n) {

        var arr = new int[n];

        arr[0] = 1;
        arr[1] = 1;

        for (var i = 2; i < n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }

        return arr;
    }
}